package com.alg;

import com.wowox.base.utils.HashUtil;

import java.util.Arrays;

/**
 * @author: sun.hongliang
 * @create: 2019/12/28 11:40
 */
public class SortTest {
    public static void main(String[] args) {
        System.out.println(HashUtil.crc32("asx0H082CbTv"));
        int arr[] = {2, 1, 9, 3, 10, 4, 9, 8, 7};
        headSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序
     */
    public static void insertSort(int[] nums) {
        int len = nums.length;
        for (int i = 1; i < len; i++) {
            int temp = nums[i];
            if (temp > nums[i - 1])
                continue;
            for (int j = i - 1; j >= 0; j--) {
                if (temp < nums[j]) {
                    nums[j + 1] = nums[j];
                } else {
                    nums[j + 1] = temp;
                    break;
                }
            }
        }
    }

    /**
     * 冒泡排序
     */
    public static void maopaoSort(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 希尔排序
     */
    public static void shellSort(int[] arr) {
        int len = arr.length;
        int gap = len / 2;
        while (gap >= 1) {
            for (int i = gap; i < len; i++) {
                for (int j = i; j >= gap; j -= gap) {
                    if (arr[j] > arr[j - gap]) {
                        break;
                    }
                    int temp = arr[j];
                    arr[j] = arr[j - gap];
                    arr[j - gap] = temp;
                }
            }
            gap = gap / 2;
        }
    }

    /**
     * 快速排序
     */
    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return;
        int temp = arr[start];
        int i = start, j = end;
        while (i < j) {
            while (i < j && arr[i] < temp) {
                i++;
            }
            while (i < j && arr[j] > temp) {
                j--;
            }
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            i++;
            j--;
        }
        arr[i] = temp;
        quickSort(arr, start, i - 1);
        quickSort(arr, i + 1, end);
    }

    /**
     * 归并排序
     */
    public static void mergeSort(int[] arr, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) >> 1;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }

    private static void merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p = start, q = mid + 1;
        int k = 0;
        while (p <= mid && q <= end) {
            if (arr[p] < arr[q]) {
                temp[k++] = arr[p++];
            } else {
                temp[k++] = arr[q++];
            }
        }

        while (p <= mid) {
            temp[k++] = arr[p++];
        }

        while (q <= end) {
            temp[k++] = arr[q++];
        }
        k = 0;
        for (int i = start; i <= end; i++) {
            arr[i] = temp[k++];
        }
    }


    /**
     * 堆排序
     */
    public static void headSort(int[] list) {
        for (int i = (list.length) / 2 - 1; i >= 0; i--) {
            headAdjust(list, i, list.length);
        }
        for (int i = list.length - 1; i >= 1; i--) {
            swap(list, 0, i);
            headAdjust(list, 0, i);
        }
    }

    private static void headAdjust(int[] list, int i, int len) {
        for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
            if (k + 1 < len && list[k] < list[k + 1]) {
                k++;
            }
            if (list[k] > list[i]) {
                swap(list, k, i);
                i = k;
            } else {
                break;
            }
        }
    }

    private static void swap(int[] list, int k, int r) {
        int temp = list[k];
        list[k] = list[r];
        list[r] = temp;
    }
}